/* This file contains the backtracking algorithm 
* 
* 
*/   

#include "sudoku.h" 
#include "backtrack.h" 
#include "fifo.h" 
#include "scheduler.h" 

/* 
*	Performs recursive backtrack to find solution. Must provide a valid markup. 
*/  
bool g_terminate = FALSE;
extern unsigned long long begin_time;
extern int nt;

void pBacktrack (void *args)  
{
	pBTInput input = (pBTInput) args;
	Grid g = (Grid) input->g;
	Stack s = (Stack) input->s;
	pBTInput rInput;
	int trialNum;
	cellCoord currCell;
	Grid trialGrid;
	
	if (isGridSolved (g))	// Recursive base case 
	{
		prtGrid (g, 1);
		delGrid (g);
		free (args);
		g_terminate = TRUE;
		terminateProcessors (s, nt);
		printf ("Total Time: %llu\n", rdtsc () - begin_time);		
		return;
	}
	
	// Guess solutions for the candidate cell 
	for (trialNum = 0; trialNum < GRID_SIZE; trialNum++)	
	{
		if (g_terminate == TRUE)		
		{
			return;
		}
		
		// Get the cell with the least number of possibilities 
		currCell = getLeastPossCell (g);
		if ((0x1 << trialNum) & gridIndex (g, currCell.x, currCell.y))	// This is a possible number 
		{			
			// Save current grid 
			trialGrid = newGrid ();
			if (trialGrid == NULL)
			
			{
				printf ("Out of memory: trialGrid.");
				return;
			}
			memcpy (trialGrid, g, sizeof (cell) * NUM_CELLS);
			
			// Set the number 
			setCell (trialNum + 1, &gridIndex (trialGrid, currCell.x, currCell.y));
			
			// Markup cells resulting from the change 
			markup (trialGrid);
			
			// Recursively call backtrack on next cell 
			rInput = (pBTInput) malloc (sizeof (BTInput));
			if (rInput == NULL)	
			{
				printf ("Out of memory: rInput.");
				return;
			}
			
			rInput->g = trialGrid;
			rInput->s = s;
			schedule (s, &pBacktrack, (void *) rInput);
		}
	}   
	// No more cells to check. Dead end.  
	//printf("Deadend\n"); 
	delGrid (g);
	free (args);
	return;
}


